|
In abstract rewriting, an object is in normal form if it cannot be rewritten any further. Depending on the rewriting system and the object, several normal forms may exist, or none at all. ==Definition== Stated formally, if (''A'',→) is an abstract rewriting system, some ''x''∈''A'' is in normal form if no ''y''∈''A'' exists such that ''x''→''y''. For example, using the term rewriting system with a single rule ''g''(''x'',''y'')→''x'', the term ''g''(''g''(4,2),''g''(3,1)) can be rewritten as follows, applying the rule to the outermost occurrence 〔each occurrence of ''g'' where the rule is applied is highlighted in boldface〕 of ''g'': :''g''(''g''(4,2),''g''(3,1)) → ''g''(4,2) → 4. Since no rule applies to the last term, 4, it cannot be rewritten any further, and hence is a normal form of the term ''g''(''g''(4,2),''g''(3,1)) with respect to this term rewriting system. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Normal form (abstract rewriting)」の詳細全文を読む スポンサード リンク
|